/*
Edit Distance Total Accepted: 38979 Total Submissions: 147707 My Submissions Question Solution
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character
*/
#include <iostream>
#include "print.h"
#include <vector>
#include <algorithm>

using namespace std;


/***/
//Definition for an interval.
struct Interval {
	int start;
	int end;
	Interval() : start(0), end(0) {}
	Interval(int s, int e) : start(s), end(e) {}
};

class Solution {
public:
	int minDistance(string word1, string word2) {
		int size1 = word1.size(), size2 = word2.size();
		
		if (size1 == 0)
		{
			return size2;
		}
		if (size2 == 0)
		{
			return size1;
		}

		vector<vector<int> > dp(size1 + 1, vector<int>(size2 + 1));

		for (int i = 0; i <= size1; i++)
		{
			dp[i][0] = i;
		}
		for (int j = 0; j <= size2; j++)
		{
			dp[0][j] = j;
		}

		int cost = 0;
		for (int i = 1; i <= size1; i++)
		{
			for (int j = 1; j <= size2; j++)
			{
				cost = (word1[i - 1] == word2[j - 1]) ? 0 : 1;
				dp[i][j] = min(dp[i - 1][j - 1] + cost, min(dp[i][j - 1] + 1, dp[i - 1][j]+1));
			}

		}

		return dp[size1][size2];
	}
};

struct Foo
{
	Foo(){ }
	Foo(int){ }
	void fun() { }

};

void test()
{
	int a = 1, b = 2, c = 3, d = 4;
	int e = (a < b ? a : c < d ? a : d);
	cout << e << endl;
}

int main()
{
	//int a[] = { 1, 1, 2 };
	string word1 = "a", word2 = "ab";
	Solution s;
	
	int res = s.minDistance(word1,word2);



	system("pause");
	return 0;
}